package listbyorder.access101_200.test105;

import listbyorder.utils.TreeNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/7 9:42
 */
public class Solution1 {

    // 方法一： 自己写的方法，左右指针的位置严格下标
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) return null;
        return getAns(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode getAns(int[] preorder, int s1, int e1, int[] inorder, int s2, int e2) {
        if (s1 == e1) {
            return new TreeNode(preorder[s1]);
        }
        int root_val = preorder[s1];
        TreeNode root = new TreeNode(root_val);
        int in_site = 0;
        for (int i = s2; i <= e2; i++) {
            if (inorder[i] == root_val) {
                in_site = i;
                break;
            }
        }
        if (in_site == s2) {
            root.right = getAns(preorder, s1 + 1, e1, inorder, s2 + 1, e2);
        } else if (in_site == e2) {
            root.left = getAns(preorder, s1 + 1, e1, inorder, s2, e2 - 1);
        } else {
            int left_len = in_site - s2;
            int right_len = e2 - in_site;
            root.left = getAns(preorder, s1 + 1, s1 + left_len, inorder, s2, in_site - 1);
            root.right = getAns(preorder, e1 - right_len + 1, e1, inorder, in_site + 1, e2);
        }
        return root;
    }

}
